package com.caoyanan.algorithm.question.zuoTraining.training004.class01;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * 给定一个数组arr，再给定一个k值
 * 返回累加和小于等于k，但是离k最近的子数组累加和
 * @author: caoyanan
 * @time: 2021/5/26 23:39
 */
public class Question04_SubArraySumK {

    public static void main(String[] args) {

        int count = 10000;
        int k = 50;
        for (int i = 0; i < count; i++) {
            int[] arr = LogarithmInputGenerator.getInstance()
                    .generateRandomArray(10, 10);
            int violenceResult = violenceMethod(arr, k);
            int prefixSumResult = prefixSumMethodSolveLessThanOrEqualToKQuestion(arr, k);
            if (violenceResult != prefixSumResult) {
                System.out.printf("数组:%s,K:%s,  暴力结果:%s, 前缀和数组结果:%s \n",
                        Arrays.toString(arr), k, violenceResult, prefixSumResult);
            }
        }

    }


    /**
     * 暴力方法
     */
    private static int violenceMethod(int[] arr, int k) {
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                if (sum <= k) {
                    result = Math.max(result, sum);
                }
            }
        }
        return result;
    }

    /**
     * 给一个数组arr和k，求arr子数组的和小于等于k，且距离k最近
     * 思考：这个子数组必然以数组中的某个位置为结尾，所以遍历每个结尾位置，必然会得到结果
     * 然后，比如以i位置为结尾的哪个子数组，小于等于k，且距离k最近
     * 这时候可以暴力遍历，时间复杂度O(n),总体O(n^2)，也可以构建一个前缀和数组，求大于等于sum-k的最小值是什么，
     * sum 减去 这个最小值 就是以i位置为结尾的最大的小于等于k的数，然后依次迭代每个位置，就可以得到最后的答案
     * 规定：子数组不包含空数组，如果没有这样的子数组，输出整型的最小值
     * @param arr
     * @param k
     */
    private static int prefixSumMethodSolveLessThanOrEqualToKQuestion(int[] arr, int k) {

        if (arr == null || arr.length == 0) {
            return 0;
        }
        TreeSet<Integer> prefixSum = new TreeSet<>();
        int result = Integer.MIN_VALUE;
        //一开始就有一个前缀和为0的情况，比如输入arr={5}, k=10,结果就是5
        prefixSum.add(0);
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            Integer biggerThanNumberMinData = prefixSum.ceiling(sum-k);
            if (biggerThanNumberMinData != null) {
                result = Math.max(result, sum - biggerThanNumberMinData);
            }
            prefixSum.add(sum);
        }
        return result;
    }
}
